package hash;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;



public class Test2 {
    public static void main(String[] args) {
      String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> lists = groupAnagrams(strs);
    }
    public static List<List<String>> groupAnagrams(String[] strs) {
        int n = strs.length;
        int right = n - 1;
        int left = 0;
        boolean[] visited = new boolean[200];
        List<List<String>> res = new ArrayList<>();
        while(left < n) {
            while (visited[left]) {
                left++;
            }

            List<String> group = new ArrayList<>();
            group.add(strs[left]);
            visited[left] = true;

            right = n - 1;
            while (left < right) {
                boolean flagA = hashFun1(strs[left], strs[right]);
                if (!flagA || visited[right]) {
                    right--;
                }
                visited[right] = true;
                right--;
            }
            res.add(group);
            left++;
        }
        return res;
    }
    // 判断两个字符串是否是异位词
    private static boolean hashFun1(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;
        for (char c : t.toCharArray()) {
            if (--count[c - 'a'] < 0) return false;
        }
        return true;
    }
}
